import java.util.HashMap;
import java.util.Map;

/**
 * 面试题50：第一个只出现一次的字符
 */
public class Offer_50 {
    /**
     * 哈希表 + 两次遍历
     * <p>
     * 时间复杂度：O(n)
     * <p>
     * 空间复杂度：O(26)=O(1)
     */
    public char firstUniqChar(String s) {
        char[] charArray = s.toCharArray();
        // 题目中给出只包含小写字母，也可以用数组代替哈希表
        // key 为字符，value 为该字符在字符串中出现的次数
        Map<Character, Integer> map = new HashMap<>();
        // 第一次遍历，统计各字符出现的次数
        for (char c : charArray) {
            map.put(c, map.getOrDefault(c, 0) + 1);
        }
        // 第二次遍历，找出答案
        for (char c : charArray) {
            if (map.get(c) == 1) {
                return c;
            }
        }
        return ' ';
    }
}
